from typing import List


# 188. 买卖股票的最佳时机 IV
# 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
# 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
def maxProfit(k: int, prices: List[int]) -> int:
    buy = [-prices[0] for _ in range(k)]
    sell = [0 for _ in range(k)]

    for day in range(1, len(prices)):
        price = prices[day]

        for i in range(len(buy)):

            if i == 0:
                buy[i] = max(buy[i], -price)
                sell[i] = max(sell[i], buy[i] + price)
                continue

            buy[i] = max(buy[i], sell[i - 1] - price)
            sell[i] = max(sell[i], buy[i] + price)

    return sell[k - 1]


k_1 = 2
prices_1 = [2, 4, 1]
result = maxProfit(k_1, prices_1)
print(f"result:{result}")

k_1 = 2
prices_1 = [3, 2, 6, 5, 0, 3]
result = maxProfit(k_1, prices_1)
print(f"result:{result}")


k_1 = 1
prices_1 = [1, 7, 1, 7, 1, 7, 1, 7]
result = maxProfit(k_1, prices_1)
print(f"result:{result}")

k_1 =2
prices_1 = [1, 7, 1, 7, 1, 7, 1, 7]
result = maxProfit(k_1, prices_1)
print(f"result:{result}")

k_1 = 3
prices_1 = [1, 7, 1, 7, 1, 7, 1, 7]
result = maxProfit(k_1, prices_1)
print(f"result:{result}")

k_1 = 4
prices_1 = [1, 7, 1, 7, 1, 7, 1, 7]
result = maxProfit(k_1, prices_1)
print(f"result:{result}")